Partie 1/3 : Représentations vectorielles

François HU - ENSAE - 14/04/20 - https://curiousml.github.io/

In [4]:
from jyquickhelper import add_notebook_menu
add_notebook_menu()
Out[4]:
run previous cell, wait for 2 seconds

Quelques motivations :

  • contextes non-supervisé
  • représenter numériquement des mots de sorte que la relation suivante ait un sens :

vect(king) - vect(man) + vect(woman) = vect(queen)

  • représenter numériquement des thèmes (topics) cachés et les documents :

    • créer des systèmes de recommandation (utilisés par les e-commerçants, les moteurs de recherche, la publicité digitale, ...)
    • catégorisation de textes
    • processus d'exploration des données
    • en bio-informatique : extraire des connaissances cachées des données biologiques
    • ...

1. Word Embeddings

$\color{grey}{\text{*cacher le code}}$

In [2]:
from IPython.display import HTML, Image
HTML('''<script>code_show=true; function code_toggle() {if (code_show){$('div.input').hide();} else {$('div.input').show();}code_show = !code_show} $( document ).ready(code_toggle);</script><form action="javascript:code_toggle()"><input type="submit" value="cacher / afficher code"></form>''')
Out[2]:

Représentation vectorielle des mots : one-hot encoding ?

In [26]:
Image("img/vectBOW1.png", width=700, height = 200)
Out[26]:
In [27]:
Image("img/vectBOW2.png", width=750, height = 200)
Out[27]:
In [28]:
Image("img/vectBOW3.png", width=750, height = 200)
Out[28]:

remarques :

  • approche naïve de vectorisation des mots : approche one-hot, approche TF-IDF
  • one-hot et TF-IDF sont des vecteurs creux (sparse en anglais) de grandes dimensions
  • one-hot et TF-IDF sauvegardent les mots sans prendre en compte le contexte : vect("content") $\neq$ vect("satisfait")

solution : approche word embedding

Word embedding

$\color{#228B22}{\text{word embedding}}$ (plongement de mots en français) : vectorisation des mots de sorte que les mots apparaissant dans des contextes similaires ont des significations apparentées

In [25]:
Image("img/vectWE.png", width=700, height = 200)
Out[25]:
  • vecteurs denses de plus petites dimensions
  • mot1 $\approx$ mot2 $\implies$ word_embedding(mot1) $\approx$ word_embedding(mot2)
  • word embedding populaire : word2vec

word2vec

  • principe : utiliser les réseaux de neurones pour construire ces vecteurs
  • deux architectures de réseaux de neurones word2vec : continuous bag-of-words (CBOW) ou skip-gram
  • $\color{#228B22}{\text{modèle CBOW}}$ : cherche à prédire un mot à partir du contexte
  • $\color{#228B22}{\text{modèle skip-gram}}$ : cherche à prédire les mots du contexte à partir d'un mot central
  • $\color{#228B22}{\text{contexte, cible}}$ :
In [43]:
display(Image("img/context_word.gif.png", width=500, height = 200))

Introduction au CBOW

In [29]:
display(Image("img/CBOW_1.png", width=500, height = 200))

CBOW

In [30]:
display(Image("img/CBOW_2.png", width=700, height = 200))

Introduction au skip-gram

In [31]:
Image("img/SG_1.png", width=500, height = 200)
Out[31]:

Skip-gram

In [32]:
Image("img/SG_2.png", width=700, height = 200)
Out[32]:

Skip-gram : un peu de mathématiques

  • prédire les mots du contexte sachant le mot central :
$$p(w_{t-h}, \dots, w_{t+h} \ |\ w_t; \theta) = \prod\limits_{-h \leq k\leq h \ ,\ k\neq0} p(w_{t+k}\ | \ w_t ; \theta) $$
  • calculer (et maximiser) la proba du paramètre sachant les mots : vraisemblance $$L(\theta) = \prod\limits_{t=1,\dots, T} p(w_{t-h}, \dots, w_{t+h} \ |\ w_t; \theta) = \prod\limits_{t=1,\dots, T} \prod\limits_{-h \leq k\leq h \ ,\ k\neq0} p(w_{t+k}\ | \ w_t ; \theta)$$
  • log-vraisemblance : $$\mathcal{L}(\theta) = -\frac{1}{T}\log L(\theta) = -\frac{1}{T}\sum\limits_{t=1,\dots,T}\sum\limits_{-h\leq k\leq h\ , \ k\neq0}\log p(w_{t+k}\ | w_t ; \theta)$$
  • softmax et paramètre: $$p(w_O\ | \ w_I) = \frac{e^{<{v'}_{w_O}\ ,\ v_{w_I}>}}{\sum\limits_{w\in V}e^{<{v'}_{w}\ ,\ v_{w_I}>}} \ , \ \theta = [{v}_{w_1}, \cdots, v_{w_{|V|}}, {v'}_{w_1}, \cdots] \in \mathbb{R}^{2\cdot N\cdot|V|}$$
  • algorithme de descente de gradient pour entraîner notre modèle
  • problème : le calcul de softmax est trop long
  • solutions : softmax hierarchique ou negative sampling

$\color{#228B22}{\text{Softmax hierarchique}}$ :

https://www.quora.com/What-is-hierarchical-softmax

$\color{#228B22}{\text{Negative sampling}}$ :

http://mediamining.univ-lyon2.fr/people/guille/word_embedding/skip_gram_with_negative_sampling.html

classification de textes avec word2vec

agrégation puis classification classique :

In [27]:
Image("img/doc_som_moy.png", width=650, height = 200)
Out[27]:
In [28]:
Image("img/doc_som_moypond.png", width=700, height = 200)
Out[28]:

doc2vec puis classification classique : voir $\color{red}{\text{section suivante}}$ pour le modèle doc2vec

classification avec les réseaux de neurones : voir $\color{red}{\text{cours 2}}$ pour les modèles séquentiels

doc2vec

vectorisation des documents (resp. des mots) de sorte que les documents (resp. les mots) apparaissant dans des contextes similaires ont des significations apparentées

$\color{#228B22}{\text{Distributed Memory (DM)}}$ :

$$p(w_i\ | \ w_{i-h}, \dots, w_{i+h}, d)$$
In [33]:
Image("img/DM.png", width=700, height = 200)
Out[33]:

$\color{#228B22}{\text{Distributed Bag-Of-Words (DBOW)}}$ :

$$p(w_{i-h}, \dots, w_{i+h} \ | \ d)$$
In [34]:
Image("img/DBOW.png", width=700, height = 200)
Out[34]:

Résumé

  • word embedding :
    • word2vec : CBOW et skip-gram
  • doc embedding :
    • doc2vec : DM et DBOW
  • classification de textes avec ces embeddings
In [11]:
Image("img/cartoon_w2v.png", width=580, height = 200)
Out[11]:

auteur : Dmitry Malkov, data scientist et dessinateur de BD chez Data Monsters

2. Topic modeling

$\color{grey}{\text{*cacher le code}}$

In [2]:
from IPython.display import HTML, Image
HTML('''<script>code_show=true; function code_toggle() {if (code_show){$('div.input').hide();} else {$('div.input').show();}code_show = !code_show} $( document ).ready(code_toggle);</script><form action="javascript:code_toggle()"><input type="submit" value="cacher / afficher code"></form>''')
Out[2]:

représentation vectorielle des documents / topics

  • $\color{#228B22}{\text{topic modeling}}$ (modèle thématique en français) : processus d'identification des topics (ou thèmes) permettant de décrire un ensemble de documents

hypothèses :

  • chaque document est vu comme un mélange de topics
  • chaque topic est vu comme une collection de mots
In [3]:
Image("img/TM.png", width=350, height = 200)
Out[3]:

topic models les plus populaires : LSA, PLSA, LDA

Latent Semantic Analysis (LSA)

In [12]:
Image("img/LSA_schema.png", width=700, height = 200)
Out[12]:

1. encodage en une matrice A

  • encodage par one-hot (voir $\color{red}{\text{introduction}}$)
  • encodage par TF-IDF (voir $\color{red}{\text{introduction}}$)

2. factorisation de la matrice A par SVD tronquée

  • $\color{#228B22}{\text{Décomposition en Valeurs Singulières}}$ (SVD) :
In [4]:
Image("img/SVD.png", width=480, height = 200)
Out[4]:
  • $\color{#228B22}{\text{SVD tronquée}}$
In [5]:
Image("img/SVDt.png", width=480, height = 200)
Out[5]:

Comment choisir $\tilde{U}_t$ et $\tilde{V}_t^T$ ?

  • solution 1 :
In [22]:
Image("img/SVDt2.png", width=410, height = 200)
Out[22]:
  • solution 2 :
In [21]:
Image("img/SVDt1.png", width=410, height = 200)
Out[21]:

Remarques :

  • approche algèbre linéaire

  • évaluer la similarité entre les documents (similarité cosinus)

  • évaluer la similarité entre les mots (similarité cosinus)

désavantages :

  • vecteurs difficilement interpretable

  • besoin d'un grand ensemble de docs et de vocabulaires pour obtenir une bonne précision

Probabilistic Latent Semantic Analysis (PLSA)

Idée : trouver un modèle probabiliste avec des topics latent qui peut générer les observations du matrice mots-docs

In [30]:
Image("img/topic_generated.png", width=600, height = 200)
Out[30]:

Par David Blei, Probabilistic topic models, 2012

Formellement :

Input : collection de textes bag-of-words :

$$n_{wd} = \text{ nombre d'occurence du mot } w \text{ dans le document } d $$

Trouver : probabilité que le mot $w$ soit dans un topic $t$ :

$$\phi_{wt} = p(w|t)$$

probabilité que le topic $t$ soit dans le document $d$ :

$$\theta_{td} = p(t|d)$$

comment est généré un document $d$ d'après le modèle $\color{red}{\text{PLSA}}$ ?

un document $d = (w_1, \dots, w_W)$ est généré de la manière suivante : pour tout $w \in d$

  • $t \sim Multinomial(\theta_{\cdot d}) = Multinomial(\ p(t_1|d), \ p(t_2|d), \cdots \ )$
  • $w\sim Multinomial(\phi_{\cdot t}) = Multinomial(\ p(w_1|t), \ p(w_2|t), \cdots \ )$

modèle graphique associé au PLSA :

In [33]:
Image("img/PLSA_GM.png", width=400, height = 200)
Out[33]:

écriture probabiliste

  • $p(w \ | \ d) = \sum\limits_{t\in T} p(w \ |\ t, d)\cdot p(t \ | \ d) = \sum\limits_{t\in T} p(w \ |\ t)\cdot p(t \ | \ d) = \sum\limits_{t\in T} \phi_{wt}\cdot\theta_{td}$

écriture matricielle

In [6]:
Image("img/PLSA.png", width=500, height = 200)
Out[6]:

PLSA $\approx$ aspect probabiliste de LSA

Entraînement du modèle PLSA

posons $\Theta = [\cdots\theta_{ij}\cdots]$ et $\Phi = [\cdots\phi_{ij}\cdots]$

  • calcul de la vraisemblance (objectif maximiser ce terme) : $$L(\Theta, \Phi) = \prod_d\prod_w p(d,w)^{n_{wd}} = \prod_d p(d)\prod_w p(w|d)^{n_{wd}}$$
  • calcul de la log-vraisemblance (objectif maximiser ce terme) : $$\mathcal{L}(\Theta, \Phi) = \sum_d\sum_w n_{wd} \log\sum_t\phi_{wt}\cdot\theta_{td}$$

problème : $\color{red}{\log\sum_t}$ dur à maximiser

solution : algorithme EM - https://fr.wikipedia.org/wiki/Algorithme_esp%C3%A9rance-maximisation

Latent Dirichlet Allocation (LDA)

PLSA : topic modeling basé sur une inférence fréquentiste : $\phi_t = (\phi_{wt})_{w\in W}$ et $\theta_d = (\theta_{td})_{t\in T}$ sont des variables déterministes

$\color{#228B22}{\text{LDA}}$ : topic modeling basé sur une inférence bayésienne : $\phi_t = (\phi_{wt})_{w\in W}$ et $\theta_d = (\theta_{td})_{t\in T}$ sont des variables aléatoires latentes de la distributions Dirichlet :

  • $\theta_d \sim Dir(\alpha)\ , \ \ \ \phi_t \sim Dir(\beta)$
  • $Dir(\theta_d| \alpha) = \frac{\Gamma(\sum_t\alpha_t)}{\prod_t \Gamma(\alpha_t)}\prod_t \phi_{td}^{\alpha_t - 1} \ , \ \ \ Dir(\phi_t| \beta) = \frac{\Gamma(\sum_w\beta_w)}{\prod_w \Gamma(\beta_w)}\prod_w \phi_{wt}^{\beta_w - 1}$

LDA $\approx$ extension du PLSA

Plusieurs densités de la loi de Dirichlet lorsque K = 2 (loi bêta)

In [6]:
Image("img/Beta_distribution.png", width=500, height = 200)
Out[6]:

Plusieurs images de la densité de la loi de Dirichlet lorsque K = 3

In [7]:
Image("img/Dirichlet_distributions.png", width=500, height = 200)
Out[7]:
  • Dans le sens horaire à partir du coin supérieur gauche : $\alpha =(6, 2, 2), (3, 7, 5), (6, 2, 6), (2, 3, 4)$

comment est généré un document $d$ d'après le modèle $\color{red}{\text{LDA}}$ ?

un document $d = (w_1, \dots, w_W)$ est généré de la manière suivante : pour tout $w \in d$

  • $\theta_d \sim Dir(\alpha)\ , \ \ \ \phi_t \sim Dir(\beta)$
  • $t \sim Multinomial(\theta_{\cdot d})\ , \ \ \ w\sim Multinomial(\phi_{\cdot t})$

modèle graphique associé au LDA :

In [36]:
Image("img/LDA_GM.png", width=500, height = 200)
Out[36]:
  • question : comment estimer les variables aléatoires $\theta_d$ et $\phi_t$ ?

Résumé :

  • topic modeling

  • topic models :

    • LSA, une approche d'algèbre linéaire;
    • PLSA, une inférence fréquentiste;
    • LDA, une inférence bayésienne;

  • TP sur le topic modeling